/*
 * Heap.h
 *
 *  Created on: Sep 4, 2012
 *      Author: martin
 */
#ifndef HEAP_H_
#define HEAP_H_

#include"DivisionEntera.h"

template<class c>
class Heap{

	private:
		c* datos;
		const unsigned int TAMANIO_MAXIMO;
		unsigned int tamanio;
		void restaurarHeapI();
		void restaurarHeapR();
		void intercambiar(unsigned int,unsigned int);
		bool comparar(c*,c*,c*,unsigned int*,unsigned int*,unsigned int*);

	public:
		bool estaVacio();
		bool insertar(c);
		c remover();
		c verRaiz();
		unsigned int getTamanio();
		unsigned int getTamanioMaximo();
		Heap(unsigned int);
		Heap(const Heap&);
		~Heap();

};//Heap

template<class c>
bool Heap<c>::estaVacio(){
	return (!tamanio);
}//estaVacio

template<class c>
void Heap<c>::intercambiar(unsigned int a,unsigned int b){
	if(a>=tamanio || b>=tamanio)
		return;

	c aux= datos[a];
	datos[a]=datos[b];
	datos[b]=aux;
}//intercambiar

template<class c>
void Heap<c>::restaurarHeapI(){
	if(tamanio== 1)
		return;

	if(tamanio== 2){
		if(datos[0]>datos[1])
			intercambiar(0,1);
		return;
	}

	if(tamanio== 3){
		if(datos[0]>datos[2])
			intercambiar(0,1);
		return;
	}

	c dato= datos[tamanio-1];
	unsigned int indicePadre= tamanio-1;
	indicePadre= div(indicePadre-1,2);
	unsigned int indiceDato= tamanio-1;
	c padre= datos[indicePadre];

	while(indicePadre && dato<padre){
		intercambiar(indicePadre,indiceDato);
		indiceDato= indicePadre;
		indicePadre= div(indicePadre-1,2);
		padre= datos[indicePadre];
	}

	if(!indicePadre){
		padre= datos[0];
		if(dato<padre)
			intercambiar(indiceDato,indicePadre);
	}
}//restaurarHeap

template<class c>
bool Heap<c>::insertar(c dato){
	if(tamanio== TAMANIO_MAXIMO)
		return false;

	datos[tamanio]= dato;
	tamanio++;
	restaurarHeapI();

	return true;
}//insertar

/* identifica aquel nodo con el que el dato debe intercambiar respecto a sus hijos.
 * realiza el intercambio con el menor de ellos en caso necesario y se vuelve su
 * nuevo indice*/
template<class c>
bool Heap<c>::comparar(c* d,c* h1,c* h2,unsigned int* id,unsigned int* ih1,
		unsigned int* ih2){
	if( (*d)>(*h1) || (*d)>(*h2) ){
		if( (*h1)<(*h2) ){
			intercambiar(*ih1,*id);
			*id= *ih1;
		}
		else{
			intercambiar(*ih2,*id);
			*id= *ih2;
		}

		return false;
	}

	return true;
}//comparar

template<class c>
void Heap<c>::restaurarHeapR(){
	if(!tamanio)
		return;

	if(tamanio== 1)
		return;

	if(tamanio== 2){
		if(datos[0]>datos[1])
			intercambiar(0,1);
		return;
	}

	if(tamanio== 3){
		if(datos[0]>datos[1] || datos[0]>datos[2]){
			if(datos[1]<datos[2])
				intercambiar(0,1);
			else
				intercambiar(0,2);
		}
		return;
	}

	c dato= datos[0];
	unsigned int indiceDato= 0,indiceHijo1= (indiceDato*2+1),
			indiceHijo2= (indiceDato*2+2);
	c hijo1= datos[indiceHijo1],hijo2= datos[indiceHijo2];
	bool yaRestaurado= false;

	while(indiceHijo1<tamanio && !yaRestaurado){
		yaRestaurado= comparar(&dato,&hijo1,&hijo2,
				&indiceDato,&indiceHijo1,&indiceHijo2);
		indiceHijo1= 2*indiceDato +1;
		indiceHijo2= 2*indiceDato +2;
		hijo1= datos[indiceHijo1];
		hijo2= datos[indiceHijo2];
	}

}//restaurarHeapR

template<class c>
c Heap<c>::remover(){
	if(estaVacio())
		return 0;

	c retornar= datos[0];
	intercambiar(0,tamanio-1);
	tamanio--;
	restaurarHeapR();

	return retornar;
}//remover

template<class c>
c Heap<c>::verRaiz(){
	if(estaVacio())
		return 0;

	return datos[0];
}//verRaiz

template<class c>
unsigned int Heap<c>::getTamanio(){
	return tamanio;
}//getTamanio

template<class c>
unsigned int Heap<c>::getTamanioMaximo(){
	return TAMANIO_MAXIMO;
}//getTamanioMaximo

template<class c>
Heap<c>::Heap(unsigned int t):TAMANIO_MAXIMO(t){
	tamanio= 0;
	datos= new c[TAMANIO_MAXIMO];
}//constructor

template<class c>
Heap<c>::Heap(const Heap& h):TAMANIO_MAXIMO(h.TAMANIO_MAXIMO){
	this->tamanio= h.tamanio;
	this->datos= new c[TAMANIO_MAXIMO];
	for(int i=0;i<h.tamanio;i++)
		this->datos[i]= h.datos[i];
}//constructor


template<class c>
Heap<c>::~Heap(){
	delete[] datos;
}//destructor

#endif


